#define _CRT_SECURE_NO_WARNINGS 1
#include <string>
#include <mutex>

class ConfigInfo
{
public:
	static ConfigInfo* GetInstance()
	{
		if (_sInfo == nullptr)
		{
			std::unique_lock<std::mutex> lock(_mtx);
			if (_sInfo == nullptr)
			{
				_sInfo = new ConfigInfo();
			}
		}
		return _sInfo;
	}
private:
	ConfigInfo(const ConfigInfo& sinfo) = delete;
	ConfigInfo& operator=(const ConfigInfo& sinfo) = delete;
	ConfigInfo() {};
	std::string _ip;

	static std::mutex _mtx;
	static ConfigInfo* _sInfo;
};

std::mutex ConfigInfo::_mtx;
ConfigInfo* ConfigInfo::_sInfo = nullptr;

class Solution
{
public:
    void flatten(TreeNode* root)
    {
        dfs(root);
    }
    TreeNode* dfs(TreeNode* root)
    {
        if (!root) return nullptr;
        TreeNode* left = dfs(root->left);
        TreeNode* right = dfs(root->right);
        if (left)
        {
            root->right = left;
            root->left = nullptr;
            TreeNode* cur = root;
            while (cur->right) cur = cur->right;
            cur->right = right;
        }
        else root->right = right;
        return root;
    }
};

class Solution {
public:
    vector<int> rightSideView(TreeNode* root)
    {
        if (!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<int> ret;
        while (q.size())
        {
            int sz = q.size();
            while (sz--)
            {
                TreeNode* front = q.front();
                q.pop();
                if (sz == 0) ret.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
        }
        return ret;
    }
};

class Solution
{
    int k;
    int ret = 0;
public:
    int kthSmallest(TreeNode* root, int _k)
    {
        k = _k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if (!root) return;
        dfs(root->left);
        k--;
        if (k == 0)
        {
            ret = root->val;
            return;
        }
        dfs(root->right);
    }
};
class Solution
{
    long prev = LONG_MIN;
public:
    bool isValidBST(TreeNode* root)
    {
        return dfs(root);
    }
    bool dfs(TreeNode* root)
    {
        if (!root) return true;
        bool left = dfs(root->left);
        if (!left) return false;
        if (root->val <= prev) return false;
        prev = root->val;
        bool right = dfs(root->right);
        if (!right) return false;
        return true;
    }
};
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        int n = nums.size();
        return dfs(nums, 0, n - 1);
    }
    TreeNode* dfs(vector<int>& nums, int left, int right)
    {
        if (left > right) return nullptr;
        int mid = (left + right) / 2;
        TreeNode* newnode = new TreeNode(nums[mid]);
        newnode->left = dfs(nums, left, mid - 1);
        newnode->right = dfs(nums, mid + 1, right);
        return newnode;
    }
};
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root)
    {
        if (!root) return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> ret;

        while (q.size())
        {
            vector<int> tmp;
            int sz = q.size();
            while (sz--)
            {
                TreeNode* front = q.front();
                q.pop();
                tmp.push_back(front->val);
                if (front->left) q.push(front->left);
                if (front->right) q.push(front->right);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};
class Solution
{
    int ret = 0;
public:
    int diameterOfBinaryTree(TreeNode* root)
    {
        dfs(root);
        return ret;
    }
    int dfs(TreeNode* root)
    {
        if (root == nullptr) return 0;
        int LeftHeight = dfs(root->left);
        int RightHeight = dfs(root->right);
        ret = max(ret, LeftHeight + RightHeight);
        return max(LeftHeight, RightHeight) + 1;
    }
};
class Solution {
public:
    bool isSymmetric(TreeNode* root)
    {
        return _isSymmetric(root->left, root->right);
    }
    bool _isSymmetric(TreeNode* root1, TreeNode* root2)
    {
        if (root1 == nullptr && root2 == nullptr) return true;
        if (root1 == nullptr && root2 != nullptr) return false;
        if (root1 != nullptr && root2 == nullptr) return false;

        return root1->val == root2->val && _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
    }
};
class Solution {
public:
    TreeNode* invertTree(TreeNode* root)
    {
        if (root == nullptr) return nullptr;
        TreeNode* right = invertTree(root->right);
        TreeNode* left = invertTree(root->left);
        root->left = right;
        root->right = left;
        return root;
    }
};